package com.zsj.Tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author zsj
 * @Version 1.0
 * @Date 2024/4/14 13:14
 * @Description 根据前序和中序和后序结果还原二叉树
 * 此题目有个前提  树中的节点值不能重复 要不然算法就做不到
 */
public class ConstructTreeByPreorderInorderPostorder {

    /**
     * 根据前序和中序结果还原二叉树
     *
     * @param preorder 前序数组
     * @param inorder  中序数组
     * @return 二叉树
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        /*
        思路
        前序数组的第一个数字就是根节点
         */
        //构建根节点
        int rootValue = preorder[0];
        TreeNode root = new TreeNode(rootValue);
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootValue) {
                int[] inLeft = Arrays.copyOfRange(inorder, 0, i);
                int[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);
                int[] preLeft = Arrays.copyOfRange(preorder, 1, i + 1);
                int[] preRight = Arrays.copyOfRange(preorder, i + 1, preorder.length);
                root.left = buildTree(preLeft, inLeft);//2 4
                root.right = buildTree(preRight, inRight);//3 6 7
                break;
            }
        }
        return root;
    }

    /**
     * 根据中序和后序结果还原二叉树
     *
     * @param inOrder   中序数组
     * @param postOrder 后序数组
     * @return 二叉树
     */
    public TreeNode buildTree2(int[] inOrder, int[] postOrder) {
        if (postOrder.length == 0) return null;
        //后序数组的最后一个数字是根节点
        TreeNode root = new TreeNode(postOrder[postOrder.length - 1]);
        // 切分左右子树
        for (int i = 0; i < inOrder.length; i++) {
            if (root.val == inOrder[i]) {
                //copyOfRange 方法是含头不含尾
                //拆分中序数组 左子树和右子树
                int[] inLeft = Arrays.copyOfRange(inOrder, 0, i);
                int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);

                //拆分后序数组 左子树和右子树
                int[] postLeft = Arrays.copyOfRange(postOrder, 0, i);
                int[] postRight = Arrays.copyOfRange(postOrder, i, postOrder.length - 1);

                root.left = buildTree2(inLeft, postLeft);
                root.right = buildTree2(inRight, postRight);
                break;
            }
        }
        return root;
    }


    public static void main(String[] args) {
        ConstructTreeByPreorderInorderPostorder test = new ConstructTreeByPreorderInorderPostorder();
        TreeNode root = test.buildTree(new int[]{1,2,4,3,6,7}, new int[]{4, 2, 6, 7, 3, 1});
        TreeNode root2 = test.buildTree2(new int[]{4, 2, 1, 6, 3, 7}, new int[]{4, 2, 6, 7, 3, 1});

        //123467 答案应该是一样的

        tierTraverse(root);//123467
        System.out.println("==");
        tierTraverse(root2);//123467

    }

    /**
     * 层序遍历结果
     *
     * @param root 遍历节点
     */
    private static void tierTraverse(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            for (int i = 0; i < queue.size(); i++) {
                TreeNode poll = queue.poll();
                TreeTraversal.printFormat(String.valueOf(poll.val), 31);
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
        }
    }
}
